import Util.ListNode;

public class Solution24 {

    /**
     * 三个指针，实现链表反转并返回反转后的头节点
     * @param head
     * @return
     */
    public ListNode reverseLinkedList1(ListNode head){
        ListNode reversedHead = null;
        ListNode node = head;
        ListNode pre = null;
        while (node != null){
            ListNode next = node.next;
            if (next == null)
                reversedHead = node;
            node.next = pre;
            pre = node;
            node = next;
        }
        return reversedHead;
    }

    /**
     * 递归实现
     * @param head
     * @return
     */
    public ListNode reverseLinkedList2(ListNode head){

        if (head == null || head.next == null)
            return head;
        ListNode next = head.next;
        head.next = null;
        ListNode newHead = reverseLinkedList2(next);
        next.next = head;
        return newHead;
    }
}
